package com.chengzhi.leetcode;

import java.util.*;

/**
 * @description: 链表
 * @author: ruanchengzhi
 * @create: 2020-04-13 14:27
 **/
public class ListNodeDemo {

    public static void main(String[] args) {
        ListNode one = new ListNode(1);
        ListNode two = new ListNode(2);
        ListNode three = new ListNode(3);
        ListNode four = new ListNode(4);
        ListNode five = new ListNode(5);
        one.next = two;
        two.next = three;
        three.next = four;
        four.next = five;
        printListNode(one);
        ListNode listNode = reverseList(one);
        printListNode(listNode);
//        one.next = two;
//        two.next = one;
//        detectCycle1(one);
//        one.next = new ListNode(2);
//        two.next = new ListNode(3);
//        System.out.println(mergeKLists(new ListNode[]{one, two, three}));
//        one.next = two;
//        one.next.next = three;
//        one.next.next.next = four;
//        reversePrint(one);
//        deleteNode(one, 1);
//        System.out.println(numComponents(one, new int[]{0, 1, 3}));
    }

    /**
     * 判断二叉树是否是完全二叉树
     *
     * @param root
     * @return boolean
     * @author ruanchengzhi
     * @date 2021/8/2
     */
    boolean isCompleteTreeNode(TreeNode root) {
        if (null == root) {
            return false;
        }
        List<Integer> list = new ArrayList<>();
        middleOrder(root, list);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) > list.get(i - 1)) {
                return false;
            }
        }
        return true;
    }

    void middleOrder(TreeNode node, List<Integer> list) {
        if (null == node) {
            return;
        }
        list.add(node.val);
        middleOrder(node.right, list);
        middleOrder(node.left, list);
    }


    /**
     * 817. 链表组件
     * 给定链表头结点head，该链表上的每个结点都有一个 唯一的整型值 。
     * 同时给定列表G，该列表是上述链表中整型值的一个子集。
     * 返回列表G中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表G中）构成的集合。
     *
     * @param head
     * @param G
     * @return
     */
    public static int numComponents(ListNode head, int[] G) {
        if (null == head || G.length == 0) {
            return 0;
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < G.length; i++) {
            list.add(G[i]);
        }
        int count = 0;
        while (null != head) {
            if (list.contains(head.val) && (head.next == null || !list.contains(head.next.val))) {
                count++;
            }
            head = head.next;
        }
        return count;
    }

    /**
     * 剑指 Offer 52. 两个链表的第一个公共节点
     * 输入两个链表，找出它们的第一个公共节点。
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tempA = headA;
        ListNode tempB = headB;
        while (tempA != tempB) {
            tempA = tempA == null ? headB : tempA.next;
            tempB = tempB == null ? headA : tempB.next;
        }
        return tempA;
    }

    /**
     * 剑指 Offer 18. 删除链表的节点
     * 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
     *
     * @param head
     * @param val
     * @return
     */
    public static ListNode deleteNode(ListNode head, int val) {
        if (null == head) {
            return null;
        }
        if (head.val == val) {
            return head.next;
        }
        ListNode p = head;
        ListNode pre = p;
        while (p != null) {
            if (p.val == val) {
                pre.next = p.next;
            }
            pre = p;
            p = p.next;
        }
        return head;
    }

    /**
     * 剑指 Offer 06. 从尾到头打印链表
     * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
     *
     * @param head
     * @return
     */
    public static int[] reversePrint(ListNode head) {
        if (null == head) {
            return new int[]{};
        }
        Stack<Integer> stack = new Stack<>();
        while (null != head) {
            stack.add(head.val);
            head = head.next;
        }
        int[] result = new int[stack.size()];
        int index = 0;
        while (!stack.isEmpty()) {
            result[index] = stack.pop();
            index++;
        }
        return result;
    }

    /**
     * 2. 两数相加
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;

            carry = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);

            cur = cur.next;
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;
        }
        if (carry == 1) {
            cur.next = new ListNode(carry);
        }
        return pre.next;
    }

    /**
     * 112. 路径总和
     *
     * @param root
     * @param sum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        if (null == root) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }

    /**
     * 98. 验证二叉搜索树
     *
     * @param root
     * @return
     */
    public static boolean isValidBST(TreeNode root) {
        if (null != root) {


        }
        return true;
    }

    /**
     * 104. 二叉树的最大深度
     *
     * @param root
     * @return
     */
    public static int maxDepth(TreeNode root) {
        if (null == root) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }

    /**
     * 226. 翻转二叉树
     *
     * @param root
     * @return
     */
    public static TreeNode invertTree(TreeNode root) {
        if (null == root) {
            return null;
        }
        TreeNode leftNode = invertTree(root.left);
        TreeNode rightNode = invertTree(root.right);
        root.left = rightNode;
        root.right = leftNode;
        return root;
    }

    /**
     * 合并链表
     *
     * @param lists
     * @return
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        for (int i = 0; i < lists.length; i++) {
            ListNode node = lists[i];
            while (null != node) {
                treeMap.merge(node.val, 1, (v1, v2) -> v1);
                node = node.next;
            }
        }
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        for (Map.Entry<Integer, Integer> entry : treeMap.entrySet()) {
            Integer value = entry.getValue();
            for (int i = 0; i < value; i++) {
                ListNode nextNode = new ListNode(entry.getKey());
                curr.next = nextNode;
                curr = curr.next;
            }
        }
        return dummyHead.next;
    }


    /**
     * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
     *
     * @param l1
     * @param l2
     * @return: com.chengzhi.leetcode.ListNodeDemo.ListNode
     * @author: ruanchengzhi
     * @date: 2020/8/6
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (null == l1) {
            return l2;
        }
        if (null == l2) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    /**
     * 二叉树的层序遍历
     * 3
     * / \
     * 9  20
     * /  \
     * 15  7
     * 返回其层次遍历结果：
     * <p>
     * [
     * [3],
     * [9,20],
     * [15,7]
     * ]
     *
     * @param root
     * @return: java.util.List<java.util.List < java.lang.Integer>>
     * @author: ruanchengzhi
     * @date: 2020/4/28
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (null == root) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.isEmpty() == false) {
            ArrayList<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.poll();
                list.add(curNode.val);
                if (curNode.left != null) {
                    queue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    queue.offer(curNode.right);
                }
            }
            result.add(list);
        }
        return result;
    }

    /**
     * Depth First Search 深度优先搜索
     *
     * @param root
     */
    public static void DFS(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            // 移除最后一个
            TreeNode tempNode = stack.pop();
            System.out.println(tempNode.val);
            // 后进先出
            if (tempNode.right != null) {
                stack.add(tempNode.right);
            }
            if (tempNode.left != null) {
                stack.add(tempNode.left);
            }
        }
    }

    /**
     * Breadth First Search 广度优先收搜索
     *
     * @param root
     */
    public static void BFS(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        // 先进先出
        while (!queue.isEmpty()) {
            TreeNode tempTreeNode = queue.remove();
            System.out.println(tempTreeNode.val);
            if (tempTreeNode.left != null) {
                queue.add(tempTreeNode.left);
            }
            if (tempTreeNode.right != null) {
                queue.add(tempTreeNode.right);
            }
        }
    }

    /**
     * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先
     * “对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）
     *
     * @param root
     * @param p
     * @param q
     * @return: com.chengzhi.leetcode.ListNodeDemo.TreeNode
     * @author: ruanchengzhi
     * @date: 2020/4/21
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            return root;
        }
        int val = root.val;
        // 都在左树上
        if (val > p.val && val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
            // 都在右树上
        } else if (val < p.val && val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return root;
        }
    }

    /**
     * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先
     *
     * @param root
     * @param p
     * @param q
     * @return: com.chengzhi.leetcode.ListNodeDemo.TreeNode
     * @author: ruanchengzhi
     * @date: 2020/4/21
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {
            return root;
        }
        TreeNode cur = root;
        int val;
        while (cur != null) {
            val = cur.val;
            if (val > p.val && val > q.val) {
                cur = cur.left;
            } else if (val < p.val && val < q.val) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }

    /**
     * 反转链表
     * 输入: 1->2->3->4->5->NULL
     * 输出: 5->4->3->2->1->NULL
     *
     * @param head
     * @return: com.chengzhi.leetcode.ListNode
     * @author: ruanchengzhi
     * @date: 2020/4/13
     */
    public static ListNode reverseList(ListNode head) {
        ListNode root = head;
        ListNode resultNode = new ListNode(-1);
        while (null != root) {
            ListNode node = root.next;
            root.next = resultNode.next;
            resultNode.next = root;
            root = node;
        }
        return resultNode.next;
    }

    /**
     * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null;
     *
     * @param head
     * @return: com.chengzhi.leetcode.ListNode
     * @author: ruanchengzhi
     * @date: 2020/4/13
     */
    public ListNode detectCycle(ListNode head) {
        if (null != head) {
            ListNode fast = head.next;
            ListNode slow = head;
            while (null != fast && null != fast.next) {
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) {
                    ListNode meet = slow;
                    ListNode start = head;
                    while (meet != start) {
                        meet = meet.next;
                        start = start.next;
                    }
                    return meet;
                }
            }
        }
        return null;
    }


    public static ListNode detectCycle1(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        ListNode root = head;
        while (null != root) {
            ListNode node = root;
            if (set.contains(node)) {
                return node;
            }
            set.add(node);
            root = root.next;
        }
        return null;
    }


    public static void printListNode(ListNode head) {
        ListNode root = head;
        while (null != root) {
            System.out.print(root.val + "->");
            root = root.next;
        }
        System.out.println();
    }


    static class ListNode {
        int val;
        ListNode next;

        public ListNode() {
            next = null;
        }

        ListNode(int x) {
            val = x;
            next = null;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    ;
}
